package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
 **/
public class No053_ii {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了50.20%的用户
     */
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (mid == nums[mid]) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：39 MB, 在所有 Java 提交中击败了39.62%的用户
     */
    public int missingNumber2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i - nums[i] != 0) {
                return i;
            }
        }
        return nums.length;
    }
}
